/**
 * 专门用于测试二叉树的一些工具。
 */
#ifndef _AHAMOLETT_CDS_BINTREE_TEST_TOOL_H_
#define _AHAMOLETT_CDS_BINTREE_TEST_TOOL_H_
#ifdef __cplusplus
extern "C" {
#endif

#include <stdio.h>
#include <stdlib.h>
#include <cds/cds_types.h>
#include <cds/bintree.h>

/// 用于调试的红黑树节点。
struct my_rb_node {
    struct rb_node  rb_entry;
    int key;
};
static int __keys_cmp_fun(unsigned long key1, unsigned long key2)
{
    return (*(int*)key1) - (*(int*)key2);
}
static unsigned long __get_key_fun(struct rb_node *node)
{
    struct my_rb_node *__tmp = rb_entry(node, struct my_rb_node, rb_entry);
    return (unsigned long)&__tmp->key;
}

static struct rb_root_opts __test_rb_opts = {
    .keys_cmp_fun = __keys_cmp_fun,
    .get_key_fun = __get_key_fun
};

/// 创建一个空的红黑树根节点。
static struct rb_root *CREATE_RB_TREE(void)
{
    struct rb_root *new_tree = malloc(sizeof(struct rb_root));
    if (new_tree == NULL) {
        return NULL;
    }
    if (rb_root_init(new_tree, &__test_rb_opts) == NULL) {
        free(new_tree);
        return NULL;
    }
    return new_tree;
}

/// 根据给定key值创建一个空的红黑树节点。
static struct my_rb_node *CREATE_RB_NODE(int key)
{
    struct my_rb_node *new_node = malloc(sizeof(struct my_rb_node));
    if (new_node == NULL) {
        return NULL;
    }
    if (rb_node_init(&new_node->rb_entry) == NULL) {
        free(new_node);
        return NULL;
    }
    new_node->key = key;
    return new_node;
}

/// 销毁一个红黑树节点。
static void DESTROY_RB_NODE(struct my_rb_node *node)
{
    if (node != NULL) {
        free(node);
    }
}

/// 销毁一个红黑树节点。
static void DESTROY_RB_NODE_BY_ENTRY(struct rb_node *node)
{
    if (node != NULL) {
        DESTROY_RB_NODE(rb_entry(node, struct my_rb_node, rb_entry));
    }
}

/// 销毁一整个红黑树。
static void DESTROY_RB_TREE(struct rb_root *root)
{
    struct rb_node *parent;
    struct rb_node *pos;

    if (root == NULL) {
        return;
    }
    if (root->node == NULL) {
        free(root);
        return;
    }
    
    while (!rb_node_is_leaf(root->node)) {
        parent = root->node;
        pos = root->node;
        while (!rb_node_is_leaf(pos)) {
            while (pos->left != NULL) {
                parent = pos;
                pos = pos->left;
            }
            while (pos->right != NULL) {
                parent = pos;
                pos = pos->right;
            }
        }
        if (pos == parent->left) {
            parent->left = NULL;
            DESTROY_RB_NODE_BY_ENTRY(pos);
        } else if (pos == parent->right) {
            parent->right = NULL;
            DESTROY_RB_NODE_BY_ENTRY(pos);
        }
    }
    DESTROY_RB_NODE_BY_ENTRY(root->node);
    free(root);
}

/// 以括号分层，打印给定结点开始往下的整个子树。
static void __rb_show_subtree_list(struct my_rb_node *node, int new_line)
{
    printf("[");
    if (node != NULL) {
        if (node->rb_entry.left != NULL) {
            __rb_show_subtree_list(rb_entry(node->rb_entry.left, struct my_rb_node, rb_entry), 0);
        }
        if (node == NULL || (node->rb_entry.__parent_color & 1)) {
            printf("\033[40;37m%d\033[0m", node->key);
        } else {
            printf("\033[41;37m%d\033[0m", node->key);
        }
        if (node->rb_entry.right != NULL) {
            __rb_show_subtree_list(rb_entry(node->rb_entry.right, struct my_rb_node, rb_entry), 0);
        }
    }
    printf("]");
    if (new_line) {
        printf("\n");
    }
}


#ifdef __cplusplus
}
#endif
#endif
